package leecode

import "strings"

func solveNQueens(n int) (result [][]string) {
	path := make([][]string, n, n)
	for i := 0; i < n; i++ {
		path[i] = make([]string, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			path[i][j] = "."
		}
	}
	var backtracking func(row int) //row表示当前递归到棋盘的哪一行了
	backtracking = func(row int) {
		if row == n {
			temp := make([]string, n)
			for i, rowStr := range path {
				temp[i] = strings.Join(rowStr, "")
			}
			result = append(result, temp)
			return
		}
		for i := 0; i < n; i++ {
			if isValid1(n, row, i, path) {
				path[row][i] = "Q"
				backtracking(row + 1)
				path[row][i] = "."
			}
		}
	}
	backtracking(0)
	return result
}

func isValid1(n, row, col int, path [][]string) bool {
	//检查每一列
	for i := 0; i < n; i++ {
		if path[i][col] == "Q" {
			return false
		}
	}
	//检查斜线
	for i, j := row-1, col-1; i >= 0 && j >= 0; j, i = j-1, i-1 {
		if path[i][j] == "Q" {
			return false
		}
	}
	//检查反斜线
	for i, j := row-1, col+1; i >= 0 && j < n; j, i = j+1, i-1 {
		if path[i][j] == "Q" {
			return false
		}
	}
	return true
}
